package q42_trap;

public class Solution_2 {
    public static void main(String[] args) {

    }

    public static int trap(int[] height){
        // 双指针同时开两个柱子接水。对于每一个柱子接的水，那么它能接的水=min(左右两边最高柱子）-当前柱子高度，这个公式没有问题。
        // 同样的，两根柱子要一起求接水，同样要知道它们左右两边最大值的较小值。
        // 问题就在这，假设两柱子分别为 i，j。那么就有 iLeftMax,iRightMax,jLeftMx,jRightMax 这个变量。由于 j>i ，
        // 故 jLeftMax>=iLeftMax，iRigthMax>=jRightMax.

        // 那么，如果 iLeftMax>jRightMax，则必有 jLeftMax >= jRightMax，所有我们能接 j 点的水。
        // 如果 jRightMax>iLeftMax，则必有 iRightMax >= iLeftMax，所以我们能接 i 点的水。
        // 而上面我们实际上只用到了 iLeftMax，jRightMax 两个变量，故我们维护这两个即可。
        // （题解都没说清楚，就说个 LeftMax，RightMax，谁知道为什么就可以这么做了。)
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            // 必须要强调的是：max将会先更新
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);


            // 而后再进行判断，这样才符合规律
            if (leftMax < rightMax) {
                ans += leftMax - height[left];

                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }

}
